package solution;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.*;

public class LeetCode {
	// 链表结点
	public class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

	// 二叉树结点
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	// 反转链表（给定头结点，反转整个链表）
	public ListNode reverseList(ListNode head) {
		// 两种特殊情况可直接返回
		if (head == null) {
			return null;
		}
		if (head.next == null) {
			return head;
		}
		ListNode pre = null;// 标记原来的上一个节点
		ListNode cur = head;// 标记当前节点
		while (cur != null) {
			ListNode temp = cur.next;// 用一个值暂存下一个节点，避免断链
			cur.next = pre;
			pre = cur;// 当前节点在下一轮节作为上一个节点了
			cur = temp;// 循环处理原链的后续结点
		}
		return pre;
	}

	// 反转链表进阶版（指定开始结束位置，反转这一部分）
	public ListNode reverseBetween(ListNode head, int left, int right) {
		// 反转一个元素，相当于没有反转，直接返回原链表
		if (left == right) {
			return head;
		}
		// 暂存头结点用于最终返回
		ListNode tempHead = head;
		ListNode start = null;
		ListNode startPre = null;
		ListNode end = null;
		ListNode endAfter = null;
		// 遍历链表找到四个特殊结点暂存起来
		int i = 1;
		while (head != null) {
			if (i == left) {
				start = head;// 反转开始的结点
			}
			if (i == right) {
				end = head;// 反转结束的结点
			}
			if (i == left - 1) {
				startPre = head;// 开始结点的前一个节点
			}
			if (i == right + 1) {
				endAfter = head;// 结束结点的后一个节点
			}
			head = head.next;
			i++;
		}
		// 进行反转操作
		ListNode pre = endAfter;// 特殊处理第一个开始反转的结点
		ListNode cur = start;
		while (cur != endAfter) {
			ListNode temp = cur.next;
			cur.next = pre;
			pre = cur;
			cur = temp;
		}
		if (left != 1) {
			startPre.next = pre;// 开始反转结点的next指针还要指向反转部分的头
		}
		// 两种情况返回，从头节点开始翻转和不从头结点开始翻转
		if (left != 1) {
			return tempHead;
		} else {
			return end;
		}
	}

	// 原地移除数组中指定的值
	public int removeElement(int[] nums, int val) {
		int i = 0;// 双指针
		for (int j = 0; j < nums.length; j++) {
			if (nums[j] != val) {
				nums[i] = nums[j];
				i++;
			}
		}
		return i;
	}

	// 简单的括号匹配
	public boolean isValid(String s) {
		Stack<String> stack = new Stack<String>();
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
				stack.push(s.split("")[i]);
			} else if (s.charAt(i) == ')') {
				if (stack.empty())
					return false;
				if (stack.peek().equals("(")) {
					stack.pop();
				} else {
					return false;
				}
			} else if (s.charAt(i) == ']') {
				if (stack.empty())
					return false;
				if (stack.peek().equals("[")) {
					stack.pop();
				} else {
					return false;
				}
			} else if (s.charAt(i) == '}') {
				if (stack.empty())
					return false;
				if (stack.peek().equals("{")) {
					stack.pop();
				} else {
					return false;
				}
			}
		}
		return stack.empty();
	}

	// 判断回文数
	public boolean isPalindrome(int x) {
		String intStr = Integer.toString(x);
		int len = intStr.length();
		for (int i = 0; i < len / 2; i++) {
			if (intStr.charAt(i) == intStr.charAt(len - i - 1)) {
				continue;
			} else {
				return false;
			}
		}
		return true;
	}

	// 判断无符号整型数的二进制表示中一的个数
	public int hammingWeight(int n) {
		int count = 0;
		long l = n & 0xFFFFFFFFL;
		for (int i = 31; i >= 0; i--) {
			long power = (long) this.power(2, i) & 0xFFFFFFFFL;
			if (power <= l && l > 0) {
				l -= power;
				count++;
			}
		}
		return count;
	}

	// num的power次方
	private int power(int num, int power) {
		int total = num;
		if (power == 0) {
			return 1;
		}
		for (int i = 2; i < power; i++) {
			total *= num;
		}
		return total;
	}

	// 删除数组中的重复元素，返回删除后长度
	public int removeDuplicates(int[] nums) {
		if (nums.length == 0) {
			return 0;
		}
		int count = 0;
		for (int i = 0; i < nums.length - 1; i++) {
			if (nums[i + 1] == nums[i]) {
				continue;
			}
			nums[count] = nums[i];
			count++;
		}
		nums[count] = nums[nums.length - 1];
		return count + 1;
	}

	// 最大子序和
	public int maxSubArray(int[] nums) {
		int len = nums.length;
		if (len == 1) {
			return nums[0];
		}
		int maxSub = 0;
		int count = 0;
		int maxNum = 0xFFFFFFFF;
		for (int i = 0; i < len; i++) {
			if (nums[i] < 0) {
				count++;// 记录负数的个数
				if (nums[i] > maxNum) {
					maxNum = nums[i];
				}
			}
			int sum = 0;
			for (int j = i; j < len; j++) {
				sum += nums[j];
				if (sum > maxSub) {// 没考虑数组元素全为负数的情况
					maxSub = sum;
				}
			}
		}
		if (count == len) {// 数组元素全负的情况
			return maxNum;
		}
		return maxSub;
	}

	// 在数组表示的整数基础上加1
	public int[] plusOne(int[] digits) {
		// 主要是考虑进位的问题
		int len = digits.length;
		for (int i = len - 1; i >= 0; i--) {
			if (digits[i] == 9) {
				digits[i] = 0;// 是9，考虑进位
			} else {
				digits[i] += 1;// 不是9，加一不用考虑进位问题
				break;
			}
		}
		// 还要考虑全为9的情况
		if (digits[0] == 0) {// 进位完最高位是0说明全是9
			int[] allNine = new int[len + 1];
			allNine[0] = 1;
			for (int i = 1; i < len + 1; i++) {
				allNine[i] = 0;
			}
			return allNine;
		}
		return digits;
	}

	// 爬楼梯（加数只有1和2两种，有多少种方式可以达到和n）
	/**************
	 * 动态规划经典题目************ 本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和 1.爬上 n−1
	 * 阶楼梯的方法数量。因为再爬1阶就能到第n阶 2.爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶 所以我们得到公式 dp[n] = dp[n-1]
	 * + dp[n-2] 同时需要初始化 dp[0]=1 和 dp[1]=1
	 ***************************************/
	class Solution {
		public int climbStairs(int n) {
			int dp[] = new int[n + 1];// 从0到n共n+1种方式
			dp[0] = 1;
			dp[1] = 1;// 给初值
			for (int i = 2; i <= n; i++) {
				dp[i] = dp[i - 1] + dp[i - 2];
			}
			return dp[n];
		}
	}

	// 判断两颗二叉树是否相同（传参为两颗树的根节点）
	public boolean isSameTree(TreeNode p, TreeNode q) {
		// 先序遍历两棵树，得到的序列相同则为相同
		// 要考虑某结点没有左子树的情况
		int[] order1 = new int[100];// 结点最多100个
		int[] order2 = new int[100];
		if (!p.equals(q)) {
			return false;// 根节点不一样直接返回false
		}
		return preOrder(p, order1, 0).equals(preOrder(q, order2, 0)) ? true : false;
	}

	private int[] preOrder(TreeNode root, int[] order, int i) {
		// if(root == null) {
		// order[i] = 10001;//用结点值赋值范围外的一个值表示空的区别
		// }else {
		// order[i] = root.val;
		// }
		order[i] = root.val;
		preOrder(root.left, order, ++i);
		preOrder(root.right, order, ++i);
		return order;
	}

	// 判断链表中是否有环
	public boolean hasCycle(ListNode head) {
		if (head == null) {
			return false;
		} // 链表为空的情况
		ArrayList<ListNode> list = new ArrayList<ListNode>();
		// 笨办法
		while (head.next != null) {
			list.add(head);
			head = head.next;
			if (list.contains(head)) {
				return true;
			}
		}
		return false;
	}

	// 聪明办法：快慢指针----「Floyd 判圈算法」（又称龟兔赛跑算法）
	// 快指针能追上慢指针则说明有圈存在
	public boolean hasCycle2(ListNode head) {
		if (head == null || head.next == null) {
			return false;
		}
		ListNode slow = head;
		ListNode fast = head.next;
		while (slow != fast) {
			if (fast == null || fast.next == null) {
				return false;
			}
			slow = slow.next;
			fast = fast.next.next;
		}
		return true;
	}

	// 买卖股票的最佳时机
	public int maxProfit(int[] prices) {
		// int bottom = prices[0], top = -1, profit = 0;
		// int isLeft = 0;//加一个表示bottom是否在top左边的标志
		// int j = 1;
		// for(int i = 0; i < prices.length - 1; i ++, j ++) {
		// if(prices[i] >= prices[j] && prices[j] < bottom) {
		// isLeft
		// bottom = prices[j];//更新最低点
		// }else if(prices[i] < prices[j] && prices[j] > top) {
		// top = prices[j];//更新最高点
		// }
		// }
		// if(bottom <= prices[0] && top >= 0) {//有涨有跌的情况
		// profit = top - bottom;
		// }
		//// }else if(top >= 0 && bottom > 10000) {//只涨的情况
		//// profit = top - prices[0];
		//// }
		// return profit;
		int minprice = Integer.MAX_VALUE;
		int maxprofit = 0;
		for (int i = 0; i < prices.length; i++) {
			if (prices[i] < minprice) {
				minprice = prices[i];// 用一个值记录历史最低价
			} else if (prices[i] - minprice > maxprofit) {
				maxprofit = prices[i] - minprice;// 后面只要有价格减去历史最低价超过最大利润，就更新
			}
		}
		return maxprofit;
	}

	// 判断从根节点到叶子节点是否存在路径，使得路径上的结点值加起来等于targetSum
	public boolean hasPathSum(TreeNode root, int targetSum) {
		if (root == null) {
			return false;// 搜索完了，没有路径匹配，返回false
		}
		if (root.left == null && root.right == null) {
			return targetSum == root.val;// 搜到叶子结点了，判断是否存在符合的路径
		}
		// 未搜索完，减去父节点值，往深搜索
		return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
	}

	// 有序数组转换为二叉树搜索树（平衡二叉树的构造）
	// 二叉搜索树BST的中序遍历结果即是递增序列
	public TreeNode sortedArrayToBST(int[] nums) {
		return bSTMade(nums, 0, nums.length - 1);
	}

	private TreeNode bSTMade(int[] nums, int left, int right) {
		if (left > right) {
			return null;
		}

		// 总是选择中间位置左边的数字作为根节点（也可以选择中间位置右边，同样满足要求）
		int mid = (left + right) / 2;

		TreeNode root = new TreeNode(nums[mid]);
		// root的左右子树也都是一颗平衡二叉树
		root.left = bSTMade(nums, left, mid - 1);
		root.right = bSTMade(nums, mid + 1, right);
		return root;
	}

	// 验证回文串
	public boolean isPalindrome(String s) {
		if (s.equals("")) {
			return true;// 空字符串题目说明返回真
		}
		s = s.toUpperCase();// 转成全大写
		String[] str = s.split("");
		for (int i = 0; i < str.length; i++) {// 是数字或者大写字符,不做改变
			if ((str[i].toCharArray()[0] >= 48 && str[i].toCharArray()[0] < 58)
					|| (str[i].toCharArray()[0] >= 65 && str[i].toCharArray()[0] < 91)) {
				continue;
			} else {// 不是的话将这个字符替换为空
				str[i] = "";
			}
		}
		StringBuilder sb = new StringBuilder();
		for (int k = 0; k < str.length; k++) {
			sb.append(str[k]);
		}
		s = sb.toString();// 获得处理完的字符串（只有数字和大写字母）
		for (int j = 0; j < s.length() / 2; j++) {// 依次对比首尾字符是否相等，不等返回错
			if (s.charAt(j) != s.charAt(s.length() - j - 1)) {
				return false;
			}
		}
		// 全对比完，则是回文串，返回true
		return true;
	}

	// 删除升序排列链表中的重复元素（思路清晰，秒杀，哈哈哈）
	public ListNode deleteDuplicates(ListNode head) {
		if (head == null) {
			return null;
		}
		ListNode originHead = head;
		while (head.next != null) {
			if (head.val == head.next.val) {
				head.next = head.next.next;
				continue;
			}
			head = head.next;
		}
		return originHead;
	}

	// 二进制求和
	// 字符串输入，异或操作，相同为0，不同为1（重点：考虑进位）
	public String addBinaryWrong(String a, String b) {// 投机做法（问题：字符串超过64位会溢出）
		int num1 = Integer.parseInt(a, 2);
		int num2 = Integer.parseInt(b, 2);
		int sum = num1 + num2;
		return Integer.toBinaryString(sum);
	}

	// 正确做法，考虑异或和进位
	public String addBinary(String a, String b) {
		int len;
		if (a.length() >= b.length()) {
			len = a.length() + 1;
		} else {
			len = b.length() + 1;
		}
		char[] sum = new char[len];
		int flag = 0;// 上一位进位标志
		for (int i = 0; i < a.length(); i++) {
			if (a.length() - i - 1 >= 0 && b.length() - i - 1 >= 0) {
				if (a.charAt(a.length() - i - 1) == b.charAt(b.length() - i - 1) && flag == 0) {
					if (a.charAt(a.length() - i - 1) == '1') {// 同为1的情况
						sum[len - i - 1] = '0';
						flag = 1;// 产生进位，将标志位变为1
					}
				} else if (a.charAt(a.length() - i - 1) == b.charAt(b.length() - i - 1) && flag == 1) {
					if (a.charAt(a.length() - i - 1) == '1') {
						sum[len - i - 1] = '1';
						flag = 1;// 产生进位，将标志位变为1
					}
				} else if (a.charAt(a.length() - i - 1) == b.charAt(b.length() - i - 1) && flag == 0) {
					if (a.charAt(a.length() - i - 1) == '0') {
						sum[len - i - 1] = '0';
						flag = 0;// 不产生进位，将标志位变为0
					}
				} else if (a.charAt(a.length() - i - 1) == b.charAt(b.length() - i - 1) && flag == 1) {
					if (a.charAt(a.length() - i - 1) == '0') {
						sum[len - i - 1] = '1';
						flag = 0;// 不产生进位，将标志位变为0
					}
				} else if (a.charAt(a.length() - i - 1) != b.charAt(b.length() - i - 1) && flag == 0) {
					sum[len - i - 1] = '1';
					flag = 0;// 不产生进位，将标志位变为0
				} else if (a.charAt(a.length() - i - 1) != b.charAt(b.length() - i - 1) && flag == 1) {
					sum[len - i - 1] = '1';
					flag = 1;// 产生进位，将标志位变为1
				}
			} else {
				if (flag == 1 && sum[len - i] == 0) {// 对比完还有进位时还是要在高位+1
					sum[len - i - 1] = '1';
					flag = 0;
				}
				// TODO
			}
		}
		StringBuilder sb = new StringBuilder();
		for (char temp : sum) {
			sb.append(temp);
		}
		return sum[0] == '0' ? sb.toString().substring(1) : sb.toString();
	}

	// 杨辉三角（给定阶数，返回杨辉三角）
	public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> yangHui = new ArrayList<List<Integer>>();
		for (int i = 0; i < numRows; i++) {
			List<Integer> temp = new ArrayList<Integer>(i);
			for (int j = 0; j <= i; ++j) {
				if (j == 0 || j == i) {
					temp.add(1);// 每一行的开始和结束都是1，特殊处理
				} else {
					// 除了开始和结束位置，其他元素都是由上一行的前一个元素加后一个元素形成的
					temp.add(yangHui.get(i - 1).get(j - 1) + yangHui.get(i - 1).get(j));
				}
			}
			yangHui.add(temp);
		}
		return yangHui;
	}

	// 杨辉三角（给定索引，返回杨辉三角对应的层）
	public List<Integer> getRow(int rowIndex) {
		List<Integer> oldRow = new ArrayList<Integer>();
		for (int i = 0; i <= rowIndex; i++) {
			List<Integer> newRow = new ArrayList<Integer>();
			for (int j = 0; j <= i; j++) {
				if (j == 0 || j == i) {
					newRow.add(1);
				} else {
					newRow.add(oldRow.get(j - 1) + oldRow.get(j));
				}
			}
			oldRow = newRow;

		}
		return oldRow;
	}

	// 判断给定二叉树是否是平衡二叉树
	public boolean isBalanced(TreeNode root) {
		if (root != null) {
			if (root.right == null && root.left != null) {
				if (root.left.left != null || root.left.left != null) {
					return false;
				}
			} else if (root.left == null && root.right != null) {
				if (root.right.left != null || root.right.left != null) {
					return false;
				}
			}
		}
		isBalanced(root.left);
		isBalanced(root.right);// 看看左右子树中是否存在不平衡的根节点，有直接返回false
		return true;
	}// 错解
		// TODO

	// 二叉树最大深度
	@Deprecated
	public int maxDepth0(TreeNode root) {
		if (root == null) {
			return 0;
		}
		// 这样写会超出时间限制，因为比较时递归了一次，结果返回时又递归了一次，应该用一个变量将递归结果存起来
		return maxDepth0(root.left) > maxDepth0(root.right) ? maxDepth0(root.left) + 1 : maxDepth0(root.right) + 1;
	}

	public int maxDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int lDepth = maxDepth(root.left);
		int rDepth = maxDepth(root.right);
		return lDepth > rDepth ? lDepth + 1 : rDepth + 1;
	}

	// 二叉树最小深度
	public int minDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (root.left == null && root.right == null) {
			return 1;
		}

		int min_depth = Integer.MAX_VALUE;// 初始化最小深度
		// 左右子树有不空的，则在子树中递归寻找最小深度
		if (root.left != null) {
			min_depth = Math.min(minDepth(root.left), min_depth);
		}
		if (root.right != null) {
			min_depth = Math.min(minDepth(root.right), min_depth);
		}
		// 最终结果是左子树或右子树的最小深度加1
		return min_depth + 1;
	}

	// 两数之和（2） 输入有序数组
	public int[] twoSum(int[] numbers, int target) {
		// ***********暴力解法*****************
		// int index1 = 0;
		// int index2 = 0;
		// for(int i = 0; i < numbers.length - 1; i ++) {
		// for(int j = i + 1; j < numbers.length; j ++) {
		// if(numbers[i] + numbers[j] == target) {
		// index1 = i + 1;
		// index2 = j + 1;
		// }
		// }
		// }
		// int[] res = {index1, index2};
		// return res;
		// 双指针
		int k = numbers.length - 1;// 指向最大数的指针
		for (int i = 0; i < numbers.length - 1; i++) {

			if (numbers[i] + numbers[k] < target) {
				continue;// 比目标数小时，小指针后移，大指针不动
			}

			if (numbers[i] + numbers[k] == target) {
				return new int[] { i + 1, k + 1 };
			}

			if (numbers[i] + numbers[k] > target) {
				k--;// 比目标数大时，大指针后移，小指针不动
				i--;
			}
		}
		return new int[] { -1, -1 };// 没找到时返回-1
	}

	// 主元素 ：找出一个数组中出现次数超过长度一半的数（默认存在这个树）
	public int majorityElement(int[] nums) {
		// 1.***暴力解法******
		// int len = nums.length;
		// for(int i = 0; i < len; i ++) {
		// int count = 0;
		// for(int j = i; j < len; j ++) {
		// if(nums[i] == nums[j]) {
		// count ++;
		// }
		// }
		// if(count > len / 2) {
		// return nums[i];
		// }
		// }
		// return -1;
		// 2.聪明办法 排序
		Arrays.sort(nums);
		return nums[nums.length / 2];
		// 3.摩尔投票算法 找众数
		// 4.HashMap
	}

	// 颠倒给定的 32 位无符号整数的二进制位 you need treat n as an unsigned value
	public int reverseBits(int n) {
		int rev = 0;
		for (int i = 0; i < 32 && n != 0; ++i) {
			rev |= (n & 1) << (31 - i);// 获取最低位后向左移向上一轮的最高位
			n >>>= 1;// 最低位操作完后逻辑右移出去
		}
		return rev;
	}

	// BST调整为平衡二叉树
	public TreeNode balanceBST(TreeNode root) {
		// 先中序遍历存到链表中
		// 然后从中间节点开始构造平衡二叉树
		List<Integer> list = new ArrayList<Integer>();
		inOrderAdd(root, list);
		return listToAVL(list, 0, list.size() - 1);
	}

	private void inOrderAdd(TreeNode root, List<Integer> list) {
		if (root != null) {
			inOrderAdd(root.left, list);
			list.add(root.val);
			inOrderAdd(root.right, list);
		}
	}

	private TreeNode listToAVL(List<Integer> list, int start, int end) {
		int mid = start + (end - start) / 2;
		TreeNode root = new TreeNode(list.get(mid));
		root.left = listToAVL(list, start, mid - 1);
		root.right = listToAVL(list, mid + 1, end);
		return root;
	}

	// //判断链表是否回文串
	//
	// public boolean isPalindrome(ListNode head) {
	// if(head == null) {
	// return false;
	// }
	// if(head.next == null) {
	// return true;
	// }
	// Stack<Integer> stack = new Stack<Integer>();
	// ListNode tempHead = head;
	// int count = 0;
	// while(tempHead != null) {
	// stack.push(head.val);
	// tempHead = tempHead.next;
	// count ++;
	// }
	// return true;
	// }

	// 统计所有小于非负整数 n 的质数的数量
	public int countPrimes(int n) {
		// 暴力，超时
		if (n == 0 || n == 1) {
			return 0;
		}
		int count = 0;
		// 从2开始
		for (int i = 2; i < n; i++) {
			/*
			 * i % j == 0则i % (i/j) == 0,所以遍历到j*j = i就可以了，降低时间复杂度
			 */
			for (int j = 2; j * j <= i; j++) {
				if (i % j == 0) {
					count++;// 记录大于1的非质数数目
					break;
				}
			}
		}
		return (n - 1) - (count + 1);// 返回总数减去非质数的数目
	}

	// 反转字符串中的元音字母
	public String reverseVowels(String s) {
		char[] letter = { 'a', 'e', 'i', 'o', 'u' };
		char[] temp = s.toCharArray();
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < s.length(); i++) {
			for (char c : letter) {
				if (s.charAt(i) == c) {
					list.add(i);
					break;
				}
			}
		}
		int size = list.size();
		for (int j = 0; j < size / 2; j++) {
			swap(temp[list.get(j)], temp[list.get(size - j - 1)]);
		}
		return new String(temp);
	}

	private void swap(char a, char b) {
		char temp = a;
		a = b;
		b = temp;
	}

	// 判断一个数组中是否存在重复元素
	public boolean containsDuplicate(int[] nums) {
		// 利用set集合中元素不可重复的特性判断
		Set<Integer> set = new HashSet<Integer>();
		for (int num : nums) {
			if (!set.add(num)) {// set添加元素失败，说明有重复
				return true;
			}
		}
		return false;
	}

	// 快乐数（对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果
	// 可以变为  1，那么这个数就是快乐数。）
	// 快慢指针 - 龟速赛跑算法
	public boolean isHappy(int n) {
		if (n == 1) {
			return true;
		}
		int fast = this.getNext(n);// 快指针
		int slow = n;// 慢指针
		while (slow != 1 && fast != 1) {// 不判圈的话可能会无限循环
			slow = this.getNext(slow);
			fast = this.getNext(this.getNext(fast));
			if (slow == fast) {
				return false;
			}
		}
		return true;
	}

	private int getNext(int n) {
		int totalSum = 0;
		while (n > 0) {
			int d = n % 10;// 每次获取最低位
			n = n / 10;// 除以10类似于右移，不要最低位
			totalSum += d * d;
		}
		return totalSum;
	}

	// 同构字符串（判断两个字符串是否同构，如abb和cdd同构）
	public boolean isIsomorphic(String s, String t) {
		Map<Character, Character> map1 = new HashMap<Character, Character>();
		Map<Character, Character> map2 = new HashMap<Character, Character>();
		for (int i = 0; i < s.length(); i++) {
			if (!map1.containsKey(s.charAt(i))) {
				map1.put(s.charAt(i), t.charAt(i));
			} else {
				if (map1.get(s.charAt(i)) != t.charAt(i)) {// 出现重复字符，看另一个串的字符是否也重复
					return false;
				}
			}
			if (!map2.containsKey(t.charAt(i))) {// 以另一个串作为key
				map2.put(t.charAt(i), s.charAt(i));
			} else {
				if (map2.get(t.charAt(i)) != s.charAt(i)) {
					return false;
				}
			}
		}
		return true;
	}

	// 反转一颗二叉树
	public TreeNode invertTree(TreeNode root) {
		if (root != null) {
			TreeNode temp = root.left;
			root.left = root.right;
			root.right = temp;
		} else {
			return root;
		}
		invertTree(root.left);
		invertTree(root.right);
		return root;
	}

	// 判断传参n是不是2的幂
	public boolean isPowerOfTwo(int n) {
		// //我的思路：把n转成二进制字符串，若字符串中只有一个1，那么这个数就是2的幂,解决不了负数（补码）
		// String binary = Integer.toBinaryString(n);
		// int count = 0;
		// for(int i = 0; i < binary.length(); i ++) {
		// if(binary.charAt(i) == '1') {
		// count ++;
		// }
		// }
		// if(count == 1) {
		// return true;
		// }else {
		// return false;
		// }
		// 数学思维，O(log n)复杂度
		if (n == 0)
			return false;
		while (n % 2 == 0)
			n /= 2;
		return n == 1;
	}

	// 回文链表
	// *****************************************************************
	// 快慢指针找到链表中间节点：快指针一次走两步，慢指针一次走一步，等快指针走到表尾时，慢指针刚好到中间
	// *****************************************************************
	public boolean isPalindrome(ListNode head) {
		if (head == null) {
			return true;
		}
		// 我的思路：反转传参链表的一半，然后分开成两个链表，对比结点是否相等
		// 1.先找到中点
		ListNode slow = head;
		ListNode fast = head;
		while (fast.next != null && fast.next.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}
		// 2.反转中点以后的结点
		ListNode half = this.reverseList(slow.next); // 用slow.next是因为结点为奇数时好做while终止条件
		// 3.对比两个链表
		ListNode h = head;
		// while(h.next == slow) {
		// if(half.val != h.val) {
		// return false;
		// }else {
		// half = half.next;
		// h = h.next;
		// }
		// }
		boolean result = true;
		while (result && half != null) {
			if (h.val != half.val) {
				result = false;
			}
			h = h.next;
			half = half.next;
		}
		this.reverseList(slow);// 记得还原链表
		return true;
	}

	// BST的最近公共祖先
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if (p.equals(root) || q.equals(root)) {// 特殊情况：如果p，q中有一个是根节点的话，直接返回
			return root;
		}
		// 我的思路：由于是二叉搜索树，分三种情况，传参两个节点值都大于根节点，都小于根节点，一个大于一个小于
		// 1.一个大于一个小于，最简单情况，根节点即为它们的最近公共最先
		if ((p.val < root.val && q.val > root.val) || (p.val > root.val && q.val < root.val)) {
			return root;
		}
		// 2.其他两种情况时递归root的左右子树找到一个在左一个在右的情况
		if (p.val < root.val && q.val < root.val) {// 都小于的情况
			return lowestCommonAncestor(root.left, p, q);// 去根节点左孩子找
		}
		// 还剩一种都大于的情况（去根节点右孩子找）
		return lowestCommonAncestor(root.right, p, q);
	}

	// 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
	public ListNode removeElements(ListNode head, int val) {
		while (head != null && head.val == val) {
			head = head.next;// 头结点要删除的情况
		}
		if (head == null) {// 所有节点值都等于val的话，经过上一步，会删除完所有节点，也就是head为null了
			return head;
		}
		ListNode next = head.next;
		ListNode pre = head;
		while (next != null) {
			if (next.val == val) {// 值相等，删除 pre不动pre.next指向next.next，相当于删除了next结点，删完后next向后遍历
				pre.next = next.next;
				next = next.next;
			} else {
				pre = pre.next;
				next = next.next;
			}
		}
		return head;
	}

	// 删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
	public void deleteNode(ListNode node) {
		// 难点：传参只有要删的节点
		// 如何找到要删除节点的前一个节点？
		// !!!不用找到前一个节点，让当前节点的下一个节点成为当前节点即可
		ListNode temp = node.next;
		node.val = temp.val;
		node.next = node.next.next;
		node = temp;
	}

	// 有效的字母异位词eg：输入: s = "anagram", t = "nagaram" 输出: true
	public boolean isAnagram(String s, String t) {
		if (s.length() != t.length()) {
			return false;
		}
		// 排序
		char[] sArray = s.toCharArray();
		char[] tArray = t.toCharArray();
		Arrays.sort(sArray);
		Arrays.sort(tArray);
		// if(sArray.equals(tArray)) {//这种equals方法没有覆写，比较的是地址
		// return true;
		// }else {
		// return false;
		// }
		return Arrays.equals(sArray, tArray);// 这种覆写了，比较的是内容
	}

	public boolean isAnagram2(String s, String t) {
		// 方法2
		// 由于比较的是字母组成的字符串，且只有小写字符，故只有26种情况，用一个数组记录26个字母出现的次数即可
		if (s.length() != t.length()) {
			return false;
		}
		int[] table = new int[26];
		for (int i = 0; i < s.length(); i++) {
			table[s.charAt(i) - 'a']++;// s对应字母在记录中保存
		}
		for (int i = 0; i < t.length(); i++) {
			table[t.charAt(i) - 'a']--;// s对应字母在记录中减去
			if (table[t.charAt(i) - 'a'] < 0) {// 若有记录出现负值，说明两个字符串非异位词
				return false;
			}
		}
		return true;// 长度相等，减完没有负值出现，说明减后全变为0了，返回true
	}

	// 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的
	// 绝对值 至多为 k。
	public boolean containsNearbyDuplicate(int[] nums, int k) {
		Set<Integer> set = new HashSet<>();
		for (int i = 0; i < nums.length; ++i) {
			if (set.contains(nums[i]))
				return true;
			set.add(nums[i]);
			if (set.size() > k) {// 用大小为k的set来维持滑动窗口的大小，不用两层循环
				set.remove(nums[i - k]);
			}
		}
		return false;
	}

	// 二叉树的所有路径
	// public List<String> binaryTreePaths(TreeNode root) {
	// List<String> list = new ArrayList<String>();
	//
	// }

	// 相交链表（找出两个链表相交的起点）
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		// 利用set的不重复性
		Set<ListNode> set = new HashSet<ListNode>();
		ListNode tempA = headA;
		ListNode tempB = headB;
		while (tempA != null) {
			set.add(tempA);
			tempA = tempA.next;
		}
		while (tempB != null) {
			if (!set.add(tempB)) {
				return tempB;
			}
			tempB = tempB.next;
		}
		return null;
	}

	public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
		// 对的人终会相遇（a + both + b = b + both + a）
		if (headA == null || headB == null) {
			return null;
		}
		ListNode head1 = headA;
		ListNode head2 = headB;
		while (head1 != head2) {
			if (head1 != null) {
				head1 = head1.next;
			} else {
				head1 = headB;
			}

			if (head2 != null) {
				head2 = head2.next;
			} else {
				head2 = headA;
			}
		}
		return head1;// 没有相交最后也都走到了null，返回1 2中任一个即可
	}

	// 合并有序数组
	public void merge(int[] nums1, int m, int[] nums2, int n) {
		for (int i = m; i < m + n; i++) {
			nums1[i] = nums2[i - m];
		}
		Arrays.sort(nums1);
	}

	// 单词规律
	public boolean wordPattern(String pattern, String s) {
		String[] split = s.split(" ");
		if (pattern.length() != split.length) {
			return false;
		}
		Map<Character, String> map = new HashMap<Character, String>();
		for (int i = 0; i < pattern.length(); i++) {
			char c = pattern.charAt(i);
			if (!map.containsKey(c)) {
				if (!map.containsValue(split[i])) {
					map.put(c, split[i]);
				} else {
					return false;
				}
			} else if (!map.get(c).equals(split[i])) {
				return false;
			}
		}
		return true;
	}

	// 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
	public int missingNumber(int[] nums) {
		// 思路：给数组按升序排序，排完序后从0开始遍历数组，和索引不一致时的数即是丢失的那个
		int len = nums.length;
		Arrays.sort(nums);
		for (int i = 0; i < len; i++) {
			if (nums[i] != i) {
				return i;
			}
		}
		// 都遍历完没返回说明最后一个数n是丢失的那个数
		return len;
	}

	// 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
	public void moveZeroes(int[] nums) {
		// 暴力法(超时)
		// for(int i = 0; i < nums.length; i ++) {
		// if(nums[i] == 0) {
		// for(int j = i + 1; j < nums.length; j ++) {
		// nums[j] = nums[j - 1];
		// }
		// nums[nums.length - 1] = 0;
		// i --;
		// }
		// }
		// 双指针（left指向处理好序列的尾部，right指向未处理好的序列头部）
		int n = nums.length, left = 0, right = 0;
		while (right < n) {
			if (nums[right] != 0) {
				swap(nums, left, right);
				left++;
			}
			right++;
		}
	}

	public void swap(int[] nums, int left, int right) {
		int temp = nums[left];
		nums[left] = nums[right];
		nums[right] = temp;
	}

	// 各位相加（给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。）
	public int addDigits(int num) {
		int res = 0;
		while (num > 0) {
			int i = num % 10;// 求余取个位
			num = num / 10;// 除以10，相当于十进制右移
			res += i;
		}
		if (res > 9) {
			return addDigits(res);// 用了递归
		}
		return res;
	}

	// 二叉树的所有路径
	public List<String> binaryTreePaths(TreeNode root) {
		// 深度优先搜索解
		List<String> list = new ArrayList<String>();
		this.deepSearch(root, list, "");
		return list;
	}

	private void deepSearch(TreeNode root, List<String> list, String path) {
		if (root != null) {
			StringBuffer sb = new StringBuffer(path);
			sb.append(Integer.toString(root.val));
			if (root.left == null && root.right == null) {
				list.add(sb.toString());
			} else {
				sb.append("->");
				deepSearch(root.left, list, sb.toString());
				deepSearch(root.right, list, sb.toString());
			}
		}
	}

	// 第一个错误的版本
	public int firstBadVersion(int n) {
		// 思路：利用二分查找的思想，减少判断次数
		int left = 0;
		int right = n;
		int mid = (left + right) / 2;
		while (left < right) {
			if (isBadVersion(mid)) {
				right = mid;
			} else {
				left = mid + 1;
			}
			mid = left + (right - left) / 2;
		}
		return mid;
	}

	private boolean isBadVersion(int a) {
		return true;
	}

	// Nim 游戏
	public boolean canWinNim(int n) {
		// 脑筋急转弯，只要n是4的倍数，对手怎么都可以获胜
		return (n % 4 != 0);
	}

	// 链表的中间节点(两个中间节点的话返回后一个)
	public ListNode middleNode(ListNode head) {
		// 快慢指针，快指针一次走两步，慢指针一次走一步，快指针到尾部时，慢指针到中间‘
		ListNode fast = head.next;
		ListNode slow = head;
		while (fast != null) {
			slow = slow.next;
			if (fast.next == null) {
				return slow;
			}
			fast = fast.next.next;
		}
		return slow;
	}

	// 二叉树的层序遍历
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		if (root == null) {
			return list;// 头结点空值，返回空表
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			List<Integer> level = new ArrayList<Integer>();// 存一层的List
			int currentLevelSize = queue.size();// 当前层大小

			for (int i = 1; i <= currentLevelSize; ++i) {// 把当前层的结点存到层List
				TreeNode node = queue.poll();
				level.add(node.val);
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			list.add(level);
		}
		return list;
	}

	// 反转字符串
	public void reverseString(char[] s) {
		int len = s.length;
		for (int i = 0; i < len; i++) {
			char temp = s[i];
			s[i] = s[len - 1 - i];
			s[len - 1 - i] = temp;
		}
	}

	// 区域和检索，数组不可变
	class NumArray {
		// 可以用前缀和，把所有求和的值在构造对象时存起来，sum[right + 1] - sum[left]即为所有值
		public final int[] value;

		public NumArray(int[] nums) {
			super();
			this.value = nums;
		}

		public int sumRange(int left, int right) {
			int sum = 0;
			if (left <= right) {
				for (int i = left - 1; i < right; i++) {
					sum += this.value[i];
				}
			}
			return sum;
		}
	}

	// 3的幂
	public boolean isPowerOfThree1(int n) {
		// 方法一：用正则(先转成三进制字符串)
		return Integer.toString(n, 3).matches("^10*$");// 以1开头，后跟0~n个0
	}

	public boolean isPowerOfThree2(int n) {
		// 方法二：循环常规思路
		if (n < 1) {
			return false;
		}
		while (n % 3 == 0) {
			n /= 3;
		}

		return n == 1;
	}

	// 两个数组的交集
	public int[] intersection(int[] nums1, int[] nums2) {
		Set<Integer> set1 = new HashSet<Integer>();
		Set<Integer> set2 = new HashSet<Integer>();
		for (int num : nums1) {
			set1.add(num);
		}
		for (int num : nums2) {
			if (!set1.add(num)) {
				set2.add(num);
			}
		}
		int[] res = new int[set2.size()];
		// for(int i = 0; i < set2.size(); i ++) {
		//// res[i] =
		// }
		int i = 0;
		Iterator<Integer> it = set2.iterator();
		while (it.hasNext()) {
			res[i++] = it.next();
		}
		return res;
	}

	// 判断子序列
	public boolean isSubsequence(String s, String t) {
		// 暴力解法
		if (s.equals("")) {
			return true;
		}
		int count = 0;
		int len = s.length();
		for (int i = 0; i < t.length(); i++) {
			if (t.charAt(i) == s.charAt(count)) {
				count++;
				if (count == len) {
					return true;
				}
			}
		}
		return false;
		// 还可用动态规划解
	}

	// 不用加号和减号求两数之和
	public int getSum(int a, int b) {
		// 递归
		if (a == 0 || b == 0) {
			return a | b;
		}
		return getSum(a ^ b, (a & b) << 1);// 相当于进位了，按位与1&1才为1，左移后相当于在对应高位+1
	}

	// 字符串中的第一个唯一字符
	public int firstUniqChar(String s) {
		// hash表
		Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();// LinkedHashMap会按插入顺序遍历
		for (int i = 0; i < s.length(); i++) {
			if (!map.containsKey(s.charAt(i))) {
				map.put(s.charAt(i), i);
			} else {
				map.put(s.charAt(i), Integer.MAX_VALUE);// 用序号表示不重复，最大整数值表示重复
			}
		}

		for (Map.Entry<Character, Integer> kv : map.entrySet()) {
			if (kv.getValue() != Integer.MAX_VALUE) {
				return kv.getValue();
			}
		}

		return -1;
	}

	// 猜数字大小
	// public int guessNumber(int n) {
	//
	// }

	// 数字转为十六进制
	public String toHex(int num) {
		// return Integer.toHexString(num);
		if (num == 0) {
			return "0";
		}
		char[] chars = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
		StringBuffer buffer = new StringBuffer();
		int temp;
		while (num != 0) {
			temp = num & 15;// 每四位一转
			buffer.insert(0, chars[temp]);// insert和append的区别类似于链表头插法和尾插法的区别
			num >>>= 4;
		}
		return buffer.toString();
	}

	// 字符串相加
	public String addStrings(String num1, String num2) {
		// int flag = 0;//进位标志
		// int len1 = num1.length();
		// int len2 = num2.length();
		// int len = len1 < len2 ? len1 : len2;
		// StringBuffer sb = new StringBuffer();
		// for(int i = len - 1; i >= 0; i --) {
		// if(len1 < len2) {
		// char c1 = num1.charAt(i);
		// char c2 = num2.charAt(i + len2 - len1);
		// int c = (int)(c1 + c2) - 96;
		// if(flag == 0) {
		// sb.insert(0, c % 10);
		// }else {
		// sb.insert(0, (c % 10) + 1);
		// }
		// if(c > 9) {
		// flag = 1;
		// }else {
		// flag = 0;
		// }
		// }else {
		// char c2 = num2.charAt(i);
		// char c1 = num1.charAt(i + len1 - len2);
		// int c = (int)(c1 + c2);
		// if(flag == 0) {
		// sb.insert(0, c % 10);
		// }else {
		// sb.insert(0, (c % 10) + 1);
		// }
		// if(c > 9) {
		// flag = 1;
		// }else {
		// flag = 0;
		// }
		// }
		//
		// }
		// if(flag == 0) {
		// sb.insert(0, len1 < len2 ? num2.substring(0, len2 - len) : num1.substring(0,
		// len1 - len));
		// }else {
		// sb.insert(0, (len1 < len2 ? num2.substring(0, len2 - len) : num1.substring(0,
		// len1 - len)) + 1);
		// }
		// return sb.toString();
		int i = num1.length() - 1, j = num2.length() - 1, add = 0;// add进位标志
		StringBuffer ans = new StringBuffer();
		while (i >= 0 || j >= 0 || add != 0) {
			int x = i >= 0 ? num1.charAt(i) - '0' : 0;
			int y = j >= 0 ? num2.charAt(j) - '0' : 0;
			int result = x + y + add;
			ans.append(result % 10);
			add = result / 10;// 除以10得进位标志
			i--;
			j--;
		}
		// 计算完以后的答案需要翻转过来
		ans.reverse();
		return ans.toString();
	}

	// Fizz Buzz
	public List<String> fizzBuzz(int n) {
		List<String> list = new ArrayList<String>(n);
		for (int i = 1; i <= n; i++) {
			if (i % 3 == 0 && i % 5 == 0) {
				list.add("FizzBuzz");
			} else if (i % 3 == 0) {
				list.add("Fizz");
			} else if (i % 5 == 0) {
				list.add("Buzz");
			} else {
				list.add(Integer.toString(i));
			}
		}
		return list;
	}

	// 找到所有数组中消失的数字
	public List<Integer> findDisappearedNumbers(int[] nums) {
		List<Integer> list = new ArrayList<Integer>();
		Arrays.sort(nums);// 先排个序

		int record = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] != i + 1) {
				if (i + 1 > record) {
					list.add(i + 1);
					record = i + 1;
				}

			}
		}
		return list;
	}

	// 左叶子之和
	public int sumOfLeftLeaves(TreeNode root) {
		// 想清楚：符合条件的左叶子结点是其子节点为空，兄弟结点的子节点不空
		if (root == null) {
			return 0;
		}

		int sum = 0;
		if (root.left != null) {
			sum += isLeaf(root.left) ? root.left.val : sumOfLeftLeaves(root.left);
		}
		if (root.right != null) {
			if (!isLeaf(root.right)) {
				sum += sumOfLeftLeaves(root.right);
			}
		}
		return sum;
	}

	private boolean isLeaf(TreeNode node) {
		return node.left == null && node.right == null;
	}

	// 字符串中的单词数
	public int countSegments(String s) {
		String temp = s.trim();
		if (temp.equals("")) {
			return 0;
		}
		String[] split = temp.split("\\s+");// 正则，匹配一或多个空格
		return split.length;
	}

	// 数字的补数（求反码，假设全是正数）
	public int findComplement(int num) {
		String bit = Integer.toBinaryString(num);
		int n = bit.length();
		// 用异或，比如5（101）和7（111）全1异或就达到了按位取反的效果
		return num ^ (int) (Math.pow(2, n) - 1);
	}

	// 汉明距离总和（汉明距离：两个数二进制不同位的位数）
	public int totalHammingDistance(int[] nums) {
		// 暴力解法，超时了
		int ret = 0;
		for (int i = 0; i < nums.length; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				ret += HammingDistance(nums[i], nums[j]);
			}
		}
		return ret;
	}

	private int HammingDistance(int num1, int num2) {
		int ret = 0;
		String s1 = Integer.toBinaryString(num1);
		String s2 = Integer.toBinaryString(num2);
		int len1 = s1.length();
		int len2 = s2.length();
		// 转成二进制字符串后高位的0被舍去了，从长的那一个开始比较
		if (len1 != len2) {
			String max = Math.max(len1, len2) == len1 ? s1 : s2;
			String min = Math.min(len1, len2) == len1 ? s1 : s2;
			int dis = max.length() - min.length();
			for (int i = 0; i < dis; i++) {
				if (max.charAt(i) != '0') {
					ret++;
				}
			}
			for (int i = dis; i < max.length(); i++) {
				if (max.charAt(i) != min.charAt(i - dis)) {
					ret++;
				}
			}
		} else {
			for (int i = 0; i < s1.length(); i++) {
				if (s1.charAt(i) != s2.charAt(i)) {
					ret++;
				}
			}
		}

		return ret;
	}

	// 最大连续1的个数
	public int findMaxConsecutiveOnes(int[] nums) {
		List<Integer> list = new ArrayList<Integer>();
		int temp = 0;
		for (int i = 0; i < nums.length; i++) {
			if (i == nums.length - 1) {
				list.add(nums[i] == 1 ? temp + 1 : temp);
			}
			if ((nums[i] == 0 && temp != 0)) {
				list.add(temp);
				temp = 0;
			}

			if (nums[i] == 1) {
				temp++;
			}
		}
		int max = 0;
		for (int i : list) {
			if (i > max) {
				max = i;
			}
		}
		return max;
	}

	// 键盘行
	public String[] findWords(String[] words) {
		List<String> list = new ArrayList<String>();
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		// 给每行的字母设置一个权重，第一行为1，第二行为2，第三行为4（为4是因为，若第三行为3的话会导致有比如两个一三行的被误判为第二行比如QZ）
		char[] line1 = { 'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P', 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o',
				'p' };
		char[] line2 = { 'A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l' };
		char[] line3 = { 'Z', 'X', 'C', 'V', 'B', 'N', 'M', 'z', 'x', 'c', 'v', 'b', 'n', 'm' };
		for (char c : line1) {
			map.put(c, 1);
		}
		for (char c : line2) {
			map.put(c, 2);
		}
		for (char c : line3) {
			map.put(c, 4);
		}

		for (String word : words) {
			int len = word.length();
			int weight = 0;
			for (int i = 0; i < len; i++) {
				weight += map.get(word.charAt(i));
			}
			if (weight == len || weight == 2 * len || weight == 4 * len) {
				list.add(word);
			}
		}
		String[] ret = list.toArray(new String[list.size()]);
		return ret;
	}

	// 二叉树的直径
	int ans;

	public int diameterOfBinaryTree(TreeNode root) {
		ans = 1;
		depth(root);
		return ans - 1;
	}

	public int depth(TreeNode node) {
		if (node == null) {
			return 0; // 访问到空节点了，返回0
		}
		int L = depth(node.left); // 左儿子为根的子树的深度
		int R = depth(node.right); // 右儿子为根的子树的深度
		ans = Math.max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
		return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
	}

	// 相对名次
	public String[] findRelativeRanks(int[] score) {
		Map<Integer, String> map = new HashMap<Integer, String>();
		int[] scoreOri = score.clone();// 注意要克隆，不能直接引用
		Arrays.sort(scoreOri);
		for (int i = score.length - 1; i >= 0; i--) {
			if (i == score.length - 1) {
				map.put(scoreOri[i], "Gold Medal");
			} else if (i == score.length - 2) {
				map.put(scoreOri[i], "Silver Medal");
			} else if (i == score.length - 3) {
				map.put(scoreOri[i], "Bronze Medal");
			} else {
				map.put(scoreOri[i], (score.length - i) + "");
			}

		}
		String[] ret = new String[score.length];
		for (int i = 0; i < score.length; i++) {
			ret[i] = map.get(score[i]);
		}
		return ret;
	}

	// 检测大写字母
	public boolean detectCapitalUse(String word) {
		if (word.length() == 1) {
			return true;
		}
		if (word.charAt(0) >= 'A' && word.charAt(0) <= 'Z') {
			if (word.charAt(1) >= 'A' && word.charAt(1) <= 'Z') {
				if (word.length() > 2) {
					for (int i = 1; i < word.length(); i++) {
						if (word.charAt(i) < 'A' || word.charAt(i) > 'Z') {
							return false;
						}
					}
				}
			} else {
				if (word.length() > 2) {
					for (int i = 1; i < word.length(); i++) {
						if (word.charAt(i) >= 'A' && word.charAt(i) <= 'Z') {
							return false;
						}
					}
				}
			}
		} else {
			for (int i = 1; i < word.length(); i++) {
				if (word.charAt(i) >= 'A' && word.charAt(i) <= 'Z') {
					return false;
				}
			}
		}
		return true;
	}
	
	
	
	//完美数
    public boolean checkPerfectNumber(int num) {
    	//暴力枚举
        if (num <= 0) {
            return false;
        }
        int sum = 0;
        for (int i = 1; i * i <= num; i++) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }

            }
        }
        return sum - num == num;
    }
    
    
    
    //分糖果
    public int distributeCandies(int[] candyType) {
    	int num = candyType.length / 2;
    	Set<Integer> set = new HashSet<Integer>();
    	for(int i : candyType) {
    		set.add(i);
    	}
    	int count = set.size();
    	//对半分，最多有一半种类个数的糖（种类个数超过一半时也是），若达不到，就拿到所有种类的
    	return Math.min(num, count);
    }
    
    
    //学生出勤记录一
    public boolean checkRecord(String s) {
    	int countA = 0;
    	for(int i = 0; i < s.length(); i++) {
    		if(s.charAt(i) == 'A') {
    			countA ++;
    			if(countA > 1) {
    				return false;
    			}
    		}
    		if(i < s.length() - 2) {
    			if(s.charAt(i) == 'L' && s.charAt(i + 1) == 'L' && s.charAt(i + 2) == 'L') {
    				return false;
    			}
    		}
    	}
    	return true;
    }
    
    
    //重塑矩阵
    public int[][] matrixReshape(int[][] mat, int r, int c) {
    	int rLen = mat.length;
    	int cLen = mat[0].length;
    	
        if(rLen * cLen != r * c) {
        	return mat;
        }
        
        //二维数组的一维表示
        int[][] ans = new int[r][c];
        for (int x = 0; x < rLen * cLen; ++x) {
            ans[x / c][x % c] = mat[x / cLen][x % cLen];
        }
        return ans;
    }
    
    
    //三个数的最大乘积
    public int maximumProduct(int[] nums) {
    	int len = nums.length;
    	Arrays.sort(nums);
    	return Math.max(nums[len -1] * nums[len - 2] * nums[len - 3], nums[0] * nums[1] * nums[len - 1]);
    }
    
    
    
    //二叉树每层平均值
    public List<Double> averageOfLevels(TreeNode root){
    	List<Double> list = new ArrayList<Double>();
    	Queue<TreeNode> queue = new LinkedList<TreeNode>();
    	queue.offer(root);
    	//广度优先搜索
    	while(!queue.isEmpty()) {
    		double size = queue.size();
    		int sum = 0;
    		
    		for(int i = 0; i < size; i++) {
    			TreeNode node = queue.poll();
    			TreeNode l = node.left;
    			TreeNode r = node.right;
    			if(l != null) {
    				queue.offer(l);
    			}
    			if(r != null) {
    				queue.offer(r);
    			}
    			sum += node.val;
    		}
    		
    		list.add(sum / size);
    	}
    	return list;
    }
    
    
    //盛水最多的容器
    public int maxArea(int[] height) {
    	//暴力（超时）
//    	int max = 0;
//    	int width, length, s = 0;
//    	for(int i = 0; i < height.length; i++) {
//    		for(int j = i; j < height.length; j++) {
//    			width = height[i] > height[j] ? height[j] : height[i];//短板效应
//    			length = j - i;
//    			s = width * length;
//    			if(s > max) {
//    				max = s;
//    			}
//    		}
//    	}
//    	return max;
    	//双指针
    	int i = 0;
    	int j = height.length - 1;
    	int max = 0;
    	while(i != j) {
    		int width = height[i] > height[j] ? height[j] : height[i];//短板效应
    		int length = j -i;
    		int s = width * length;
    		if(s > max) {
    			max = s;
    		}
    		if(height[i] > height[j]) {
    			j--;
    		}else {
    			i++;
    		}
    	}
    	return max;
    }
    
    
    //x的n次幂
    public double myPow(double x, int n) {
    	//快速幂、递归
    	long N = n;
    	return N > 0 ? quickPow(x, N) : 1 / quickPow(x, -N);
    }
    private double quickPow(double x, long n) {
    	if(n == 0) {
    		return 1;
    	}
    	double y = quickPow(x, n / 2);
    	return n % 2 == 0 ? y * y : y * y * x;
    }
}
